// Basic operations for HXD1D interference graph
#include "HXD1.h"
#include "HRV64Generator.h"

const char * const HInterferenceGraph::Error = "**Error**";

/*
 * Get the degree of a vertex.
 * If `all` is not set, then for floating-point vertex, only floating-point
 * adjacencies will be considered in calculation.
 * Otherwise, just return the number of adjacencies.
 */
size_t HInterferenceGraph::degree_of(size_t vtxi, bool all) const
{
	size_t deg = 0ul;
	bool flag_float;
	if (vtxi >= vertexes_.size())
		throw std::logic_error("Invalid vertex: " + std::to_string(vtxi));
	flag_float = vertexes_.at(vtxi).is_float;
	if (all)
		deg = vertexes_.at(vtxi).degree_all();
	else
		for (auto adji : vertexes_.at(vtxi).adjlist)
			if (vertexes_.at(adji).is_float == flag_float)
				++deg;
	return deg;
}

/*
 * Add a vertex with temp `t` and return its index.
 * If it is preallocated, please set `preallocated` and `reg` valid.
 * In this case, edges between it and other preallocated vertexes
 * will be added automatically.
 * It should be deleted in derived class!
 */
size_t HInterferenceGraph::add_vertex(HIRTempno t, bool is_float,
	bool preallocated, RV64GFR reg)
{
	size_t i = vertexes_.size();
	vertexes_.push_back(HIGVertex{t, is_float, true, preallocated, reg});
	if (preallocated)
		for (size_t l = 0ul; l < i; ++l)
			if (vertexes_.at(l).allocated)
			{
				vertexes_.at(l).adjlist.insert(i);
				vertexes_.at(i).adjlist.insert(l);
			}
	return i;
}

/*
 * Add an edge between the vertexes with temp `u` and `v`.
 * The return value is reserved.
 * It should be deleted in derived class!
 */
uint64_t HInterferenceGraph::add_edge(HIRTempno u, HIRTempno v)
{
	size_t ui, vi, ci;
	ui = search_vertex(u);
	vi = search_vertex(v);
	if (ui == SIZE_MAX || vi == SIZE_MAX)
		throw std::logic_error("IG: Cannot find temp " +
			std::to_string(ui == SIZE_MAX ? u : v));
	if (u != v)
	{	// This situation should be avoided!
		vertexes_.at(ui).adjlist.insert(vi);
		vertexes_.at(vi).adjlist.insert(ui);
		// Set the copy edge constrained
		if ((ci = search_copy(ui, vi, true)) != SIZE_MAX)
			copies_.at(ci).status = HIGCopy::CONSTRAINED;
	}
	return 0ul;
}

/*
 * Add a copy edge between the vertexes with temp `u` and `v`.
 * The return value is the index of new copy edge.
 * It should be deleted in derived class!
 */
size_t HInterferenceGraph::add_copy(HIRTempno u, HIRTempno v, uint32_t inst_idx)
{
	size_t ui, vi, ci;
	ui = search_vertex(u);
	vi = search_vertex(v);
	if (ui == SIZE_MAX || vi == SIZE_MAX)
		throw std::logic_error("IG: Cannot find temp " +
			std::to_string(ui == SIZE_MAX ? u : v));
	ci = search_copy(ui, vi, true);
	if (ci == SIZE_MAX)
	{	// Add a new copy
		if (vertexes_.at(ui).is_float != vertexes_.at(vi).is_float)
			throw std::logic_error("Adding copy between floating and integer vertexes");
		ci = copies_.size();
		copies_.push_back(HIGCopy{ui, vi, inst_idx});
	}
	else
		copies_.at(ci).insts.insert(inst_idx);
	if (vertexes_.at(ui).adjlist.count(vi) > 0ul)
		// If the two temporaries are interfering...
		copies_.at(ci).status = HIGCopy::CONSTRAINED;
	return 0ul;
}

/*
 * Search a vertex with temp `t` and return its index or `SIZE_MAX` if not found.
 * It should be rewritten in derived class if needed to avoid assuming that
 * `temps` of vertex contains only one temporary.
 */
size_t HInterferenceGraph::search_vertex(HIRTempno t) const
{
	size_t i, n = vertexes_.size();
	for (i = 0ul; i < n; ++i)
	{
		auto & temps = vertexes_.at(i).temps;
		if (temps.size() != 1ul)
			throw std::logic_error("HIG: vertex " +
				std::to_string(i) + " has " +
				std::to_string(temps.size()) + " temps");
		else if (temps.count(t) > 0ul)
			// Found
			break;
	}
	return i >= n ? SIZE_MAX : i;
}

/*
 * Search a copy edge between vertex `igv1` and vertex `igv2`
 * and return its index or `SIZE_MAX` if not found.
 * `igv2` can be omitted, then it will search whether vertex `igv1`
 * has a copy edge.
 * If `any_status` is `false`, then only `NORMAL` copy edges will
 * be considered. Otherwise, all will be considered.
 */
size_t HInterferenceGraph::search_copy(size_t igv1, size_t igv2,
	bool any_status) const
{
	size_t i, n = copies_.size();
	auto it = copies_.begin();
	if (igv2 < SIZE_MAX)
	{
		for (i = 0ul; i < n; ++i, ++it)
			if (any_status || it->status == HIGCopy::NORMAL)
				if ((it->igv1 == igv1 && it->igv2 == igv2)
					|| (it->igv1 == igv2 && it->igv2 == igv1))
					break;
	}
	else
	{
		for (i = 0ul; i < n; ++i, ++it)
			if (any_status || it->status == HIGCopy::NORMAL)
				if (it->igv1 == igv1 || it->igv2 == igv1)
					break;
	}
	return i >= n ? SIZE_MAX : i;
}

/*
 * Build initial interference graph from the HXD1 IR function.
 */
const void HInterferenceGraph::build_from_hirfunct(const HIRFunct & irfunct)
{
	std::vector<BasicBlock>::const_iterator bit;
	std::vector<HIRInst>::const_iterator iit;
	std::set<HIRTempno> liveout;
	// Temps that are created by `ALLOCA` instructions
	std::set<HIRTempno> alloca_dests;

	HIRTempno dest, cpsrc;
	std::vector<HIRTempno> srctemps;

	// First, add all vertexes.
	{
		HIRTempno tn = 0u;
		uint32_t nargs_GPR = 0u, nargs_FPR = 0u;
		bool is_float, is_arg, use_reg, arg_live;
		RV64GFR areg;

		for (uint32_t i = 0u; i < irfunct.nalloca; ++i)
			alloca_dests.insert(irfunct.ircode.at(i).get_dest());

		for (auto & t : irfunct.temps)
		{
			// Skip labels and `STATIC` temps (created by `alloca`)
			if (t.type != HIRBtype::VOID && alloca_dests.count(tn) == 0ul)
			{
				is_float = (t.type == HIRBtype::DOUBLE
					|| t.type == HIRBtype::FLOAT);
				is_arg = (tn < irfunct.nparams);
				use_reg = is_arg && ((is_float && nargs_FPR < RV64_AFPR)
					|| (!is_float && nargs_GPR < RV64_AGPR));
				/*
				 * If the argument is not live (`t.localof` is valid) or
				 * is not used at all (`t.localof` is 0),
				 * then do not preallocate register for it!
				 */
				arg_live = is_arg && (t.localof == INVALID_BB_IDX);
				if (use_reg && arg_live)
					areg = RV64GFR(uint32_t(is_float ? RV64GFR::FA0 : RV64GFR::A0)
						+ (is_float ? nargs_FPR : nargs_GPR));
				else
					areg = RV64GFR::ZERO;
				add_vertex(tn, is_float, use_reg && arg_live, areg);
				/*
				 * A live argument interfers with all other live arguments,
				 * even if it is not passed by register.
				 * So we add these edges manually.
				 */
				if (arg_live && !use_reg)
					for (HIRTempno pat = 0u; pat < tn; ++pat)
						if (irfunct.temps.at(pat).localof == INVALID_BB_IDX)
							add_edge(tn, pat);

				if (use_reg && is_float)
					++nargs_FPR;
				else if (use_reg && !is_float)
					++nargs_GPR;
			}
			++tn;
		}
	}

	for (bit = irfunct.basic_blocks.begin() + 1l;
		bit != irfunct.basic_blocks.end(); ++bit)
	{
		if (bit->reachable == false)
			continue;
		iit = irfunct.ircode.begin() + bit->end;
		liveout = bit->livevar_out;
		do {
			dest = iit->get_dest();
			iit->get_srctemps(srctemps);
			if ((cpsrc = iit->is_copy()) != INVALID_TEMP_NO)
			{	// is a copy (move) instruction
				if (alloca_dests.count(cpsrc) == 0ul)
				/*
				 * If the source of the copy instruction is created by `alloca`,
				 * don't add a copy edge as it will NOT be created a vertex.
				 */
					add_copy(dest, cpsrc, iit - irfunct.ircode.begin());
				for (auto lt : liveout)
					if (lt != dest && lt != cpsrc && alloca_dests.count(lt) == 0ul)
					// Don't add edge for `alloca` temps, either!
						add_edge(dest, lt);
			}
			else
			{
				if (dest != INVALID_TEMP_NO)
					for (auto lt : liveout)
						if (lt != dest && alloca_dests.count(lt) == 0ul)
							add_edge(dest, lt);
			}
			// update `liveout`: "IN[s] = use[s] + (OUT[s] - def[s])"
			if (dest != INVALID_TEMP_NO)
				liveout.erase(dest);
			for (auto st : srctemps)
				liveout.insert(st);
		} while ((iit--) != irfunct.ircode.begin() + bit->begin);
		if (opts.debug_level > 1 && liveout != bit->livevar_in)
			// Check `liveout`
			throw std::logic_error("IN[BB#" +
				std::to_string(bit - irfunct.basic_blocks.begin()) + "] for live vars"
				" is not consistent with `liveout` while building IG"
			);
	}
}


//HWorkingIGraph::HWorkingIGraph(const HInterferenceGraph & Oig,
//	const std::set<HIRTempno> & spilled)
//	: HInterferenceGraph(Oig.vertexes(), Oig.copies())
void HWorkingIGraph::build_from_oig(const HInterferenceGraph & Oig,
	const std::set<HIRTempno> & spilled)
{
	// Initialize data members
	vertexes_ = Oig.vertexes();
	copies_ = Oig.copies();
	simplified_stack_.clear();
	// Do some necessary check
	bool checking = true;
	/*
	// `$a0` should not be allocated
	for (auto r : Available_GPR)
		if (r == RV64GFR::A0)
			checking = false;
	// `$fa0` should not be allocated
	for (auto r : Available_FPR)
		if (r == RV64GFR::FA0)
			checking = false;
	*/
	// every vertex must have one temp as coalescence is not done
	for (auto & vtx : vertexes_)
	{
		if (vtx.temps.size() != 1ul)
			checking = false;
		if (checking == false)
			break;
	}
	if (checking == false)
		throw std::logic_error("Invalid original interference graph");
	// Invalidate vertexes in spilled list
	for (auto vtx = vertexes_.begin(); vtx != vertexes_.end(); ++vtx)
		if (spilled.count(*(vtx->temps.begin())) > 0ul)
		{
			vtx->valid = false;
			vtx->allocated = false;
			vtx->temps.clear();
			for (auto adj : vtx->adjlist)
				vertexes_.at(adj).adjlist.erase(vtx - vertexes_.begin());
			vtx->adjlist.clear();
		}
}

/*
 * Search a vertex with temp `t` and return its index or `SIZE_MAX` if not found.
 * It supports that a vertex contains more than one temporaries
 * because of coalescence.
 */
size_t HWorkingIGraph::search_vertex(HIRTempno t) const
{
	size_t i, n = vertexes_.size();
	for (i = 0ul; i < n; ++i)
		if (vertexes_.at(i).valid)
		{
			if (vertexes_.at(i).temps.count(t) > 0ul)
				break;
			else if (vertexes_.at(i).temps.empty())
				throw std::logic_error("Valid vertex " + std::to_string(i)
					+ " has empty temps");
		}
	return i >= n ? SIZE_MAX : i;
}

/*
 * Print the graph into `os` with `line_prefix` starting a new line.
 * NOTE: before printing, a simple check will be done to ensure that
 *	every valid vertex only contains one temporary.
 */
void HInterferenceGraph::print(std::ostream & os, char line_prefix) const
{
	extern const char *const RV64GFR_name[];
	std::string prefix;

	if (line_prefix != '\0')
		prefix = (prefix = line_prefix) + ' ';

	if (search_vertex(INVALID_TEMP_NO) != SIZE_MAX)
		os << Error << ": invalid temp found in IG" << std::endl;

	os << prefix << "Original interference graph:" << std::endl;

	os << prefix << "\tAdjacency list:" << std::endl;
	for (auto & vtx : vertexes_)
	{
		os << prefix << "\t\t%" << *vtx.temps.begin() << ": ";
		for (auto & vtidx : vtx.adjlist)
			os << '%' << *(vertexes().at(vtidx).temps.begin()) << ", ";
		if (vtx.allocated)
			os << "Allocated: " << RV64GFR_name[uint32_t(vtx.reg)];
		os << std::endl;
	}

	os << prefix << "\tCopy edges:" << std::endl;
	for (auto & ce : copies_)
	{
		os << prefix << "\t\t(%" << *vertexes_.at(ce.igv1).temps.begin()
			<< ", %" << *vertexes_.at(ce.igv2).temps.begin() << "): ";
		for (auto i : ce.insts)
			os << i << ", ";
		if (ce.status != HIGCopy::NORMAL)
			os << "Status: " << ce.status;
		os << std::endl;
	}
}

// Print the graph into `os`
void HWorkingIGraph::print(std::ostream & os, char line_prefix) const
{
	extern const char *const RV64GFR_name[];
	std::string prefix;

	if (line_prefix != '\0')
		prefix = (prefix = line_prefix) + ' ';

	os << prefix << "Working interference graph:" << std::endl;

	os << prefix << "\tVertexes and adjacencies:" << std::endl;
	size_t vidx;
	std::vector<HIGVertex>::const_iterator vit;
	for (vidx = 0ul, vit = vertexes_.begin(); vidx < vertexes_.size(); ++vidx, ++vit)
	{
		// Type
		os << prefix << "\t\t" << (vit->is_float ? "Flt" : "Int");
		// Valid flag
		os << vidx << ": " << (vit->valid ? 'V' : 'N');
		// Temporaries
		os << " {";
		for (auto tit = vit->temps.begin(); tit != vit->temps.end(); )
		{
			os << '%' << *tit;
			if (++tit != vit->temps.end())
				os << ", ";
		}
		os << "} : ";
		for (auto adj : vit->adjlist)
			os << adj << ", ";
		if (vit->allocated)
			os << "Allocated: " << RV64GFR_name[uint32_t(vit->reg)];
		os << std::endl;
	}

	os << prefix << "\tCopy edges:" << std::endl;
	for (auto & ce : copies_)
	{
		os << prefix << "\t\t(" << ce.igv1
			<< ", " << ce.igv2 << "): ";
		// Status
		os << (
			ce.status == HIGCopy::NORMAL ? 'N' :
			ce.status == HIGCopy::COALESCED ? 'c' :
			ce.status == HIGCopy::FROZEN ? 'f' :
			ce.status == HIGCopy::CONSTRAINED ? 'i' :
			ce.status == HIGCopy::REDUNDANT ? 'r' :
			'*' // Error
		) << ' ';
		// Instructions
		for (auto i : ce.insts)
			os << i << ", ";
		os << std::endl;
	}

	os << prefix << "\tSimplified:" << std::endl;
	os << prefix << "\t\t$ ";
	for (auto spl : simplified_stack_)
		os << spl << ", ";
	
	os << std::endl;
}